import collections
import bisect

class RangeFreqQuery(object):

    def __init__(self, arr):
        """
        :type arr: List[int]
        """
        self.d = collections.defaultdict(list)
        for index, c in enumerate(arr):
            self.d[c].append(index)

    def query(self, left, right, value):
        """
        :type left: int
        :type right: int
        :type value: int
        :rtype: int
        """
        left_index = bisect.bisect_left(self.d[value], left)
        right_index = bisect.bisect_right(self.d[value], right)
        return right_index - left_index